package MiGong;
import java.awt.Point;
import java.util.ArrayList;
public class walkMaze {
    private static int[][] maze =    //建立迷宫地图，0代表可走的路，1代表墙壁不可走
                   {{1,1,1,1,1,1,1,1,1,1},
                    {1,0,0,1,0,0,0,1,0,1},
                    {1,0,0,1,0,0,0,1,0,1},
                    {1,0,0,0,0,1,1,0,0,1},
                    {1,0,1,1,1,0,0,0,0,1},
                    {1,0,0,0,1,0,0,0,0,1},
                    {1,0,1,0,0,0,1,0,0,1},
                    {1,0,1,1,1,0,1,1,0,1},
                    {1,1,0,0,0,0,0,0,0,1},
                    {1,1,1,1,1,1,1,1,1,1}};
    private static ArrayList<Point> route = new ArrayList<>();  //走迷宫的路线

    //打印输出迷宫地图
{
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze.length; j++) {
                System.out.print(maze[i][j]+"  ");
            }
            System.out.println();
        }
    }
    private static boolean isWalk(int[][] maze,Point currentPoint){
        int x = currentPoint.x;
        int y = currentPoint.y;
        //往右走
        if (maze[y][x+1]!=1 && maze[y][x+1]!=-1){
            route.add(new Point(x+1,y));
            return true;
        }
        //往下走
        if (maze[y+1][x]!=1 && maze[y+1][x]!=-1){
            route.add(new Point(x,y+1));
            return true;
        }
        //往左走
        if (maze[y][x-1]!=1 && maze[y][x-1]!=-1){
            route.add(new Point(x-1,y));
            return true;
        }
        //往上走
        if (maze[y-1][x]!=1 && maze[y-1][x]!=-1){
            route.add(new Point(x,y-1));
            return true;
        }
        return false;
    }
    private static boolean maze(int[][] maze,Point enter){
        //标记入口位置，并将入口位置加入列表中
        maze[enter.y][enter.x]=-1;
        route.add(enter);
        //判断列表是否为空
        while (!route.isEmpty()){
            while (isWalk(maze,enter)){
                //列表中的最后一个元素
                enter = route.get(route.size()-1);
                //判断改位置是否是出口位置
                if (enter.x==8 && enter.y==8){
                    return true;
                }else{
                    //标记已走过的位置
                    maze[enter.y][enter.x]=-1;
                }
            }
            //当走到死胡同的时候，回溯到前面的位置，并判断改位置是否有路可走
            // 如果有路可走，则继续往下走，反之则继续回退到前面一个位置继续查找，直到找到有路可走为止
            //将列表最后一个元素去除，并取出去除后最后的元素
            route.remove(route.size()-1);
            enter = route.get(route.size()-1);
        }
        return false;
    }
    public static void main(String[] args) {
        //走迷宫
        boolean flag = maze(walkMaze.maze, new Point(1, 1));
        if (flag){
            System.out.println("成功找到迷宫的出口！\n路线如下：");
            for (int i = 0; i < route.size(); i++) {
                System.out.print("("+route.get(i).x+","+route.get(i).y+")");
                if (i!=route.size()-1){
                    System.out.print("->");
                }
            }
        }
    }
}



